/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 * 思路：利用两个栈分别存储从根节点到p,q的路径，然后元素数量多的栈出栈直到两个栈的元素数量相等，然后两个栈同时出栈，当出栈的元素相等时，该元素就是他们最近的公共祖先
 *
 *
 */
class lowestCommonAncestorStack {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if(root==null){
           return null;
       } 
       Stack<TreeNode> stack1=new Stack<>();//存取从根节点到p的路经
       Stack<TreeNode> stack2=new Stack<>();//存取从根节点到q的路经
        findPath(root,p,stack1);
        findPath(root,q,stack2);
        int len1=stack1.size();
        int len2=stack2.size();
        if(len1<len2){
            while(len2-len1!=0){
                stack2.pop();
                len2--;
            }
            while(!stack1.isEmpty()&&!stack2.isEmpty()){
                if(stack1.peek()==stack2.peek()){
                    return stack2.peek();
                }
                stack2.pop();
                stack1.pop();
            }
        }

        else{
            while(len1-len2!=0){
                stack1.pop();
                len1--;
            }
            while(!stack1.isEmpty()&&!stack2.isEmpty()){
                if(stack1.peek()==stack2.peek()){
                    return stack2.peek();
                }
                stack2.pop();
                stack1.pop();
            }
        }
        return null;
    }
    public boolean findPath(TreeNode root,TreeNode p,Stack<TreeNode> stack){
       if(root==null||p==null)
       return false;
       stack.push(root);
       if(root==p){
           return true;
       }
       boolean fla1=findPath(root.left,p,stack);
        if(fla1==true){
            return true;
        }
        boolean fla2=findPath(root.right,p,stack);
        if(fla2==true){
            return true;
        }
        stack.pop();
        return false;
    }
}